1. Technical Field:
The invention relates to the storage and playback in real-time of digitized video signals on a digital computer, and more particularly relates to a method of data compression and decompression that supports real-time reconstruction, and display of digitized video signals on a minimal personal computer system. Still more particularly, the invention relates to a method for real-time video decompression and playback with a computational load readily carried by the central processing unit (CPU) of low-end personal computers (e.g. a computer based upon an Intel 80386SX processor running at 16 mhz) without hardware modification of the computer.
2. Description of the Related Art:
A video signal is a sequence of images or frames, which are displayed at a given frame rate (e.g., 15 to 30 frames-per-second) to simulate the appearance of motion to a human observer. In a personal computer system, each frame of digitized video includes a digital representation of each pixel in the frame. A frame may have in excess of one half a million pixels. If full frames were replaced at a frame rate in excess of 15 frames-per second, a computer would be required to recover from storage and write to video memory over seven million bytes of data each second. Few current auxiliary data storage devices have the bandwidth required to pass such levels of data. Further, storage of only a few full frames of digitized video would fill most storage devices. In low-end personal computers, the CPU handles rewriting of the video memory buffer. Rewriting of the entire buffer every one fifteenth of a second would represent an excessive load on the CPU.
In a Red-Green-Blue (RGB) color video system, color values for each of the three color components may be specified for each pixel. One to three bytes (respectively 8-bit, 16-bit and 24-bit RGB) may be used to specify color for each pixel in the frame. Conversion charts from 16 and 24 bit RGB to 8-bit RGB exist and save processing and storage space. Further, conversion charts from 8, 16 or 24-bit color representations to an 8-bit index that is used as an address to a color lookup table (or palette) can also be performed. In compressed digital video, each value or byte is used as an address into a color lookup table or palette. Typically a palette contains 256 or fewer color values selected out of a set of 2.sup.24 colors. For instance, an RGB 784 palette specifies 7 levels of red, 8 of green and 4 of blue, for a total of 224 possible color values. Thus there are values that compressed and palettized color video data does not assume. The reserved values are typically used to provide gray scale tones for monochrome video systems.
Full frame storage and recovery is rarely, if ever, used for video playback on computer systems. Digital video generation on digital computers can be achieved by using frame differencing techniques to compress the data for storage and passage to and from storage. In general terms, frame differencing codes only such information that differs from one frame to the next. In reconstruction of a frame, the old frame residing in display memory is rewritten only to the extent changed. Since few of the pixels typically change from frame to frame, frame differencing techniques save considerable storage space and substantially reduce the bandwidth demands on auxiliary storage devices. However, such techniques require processor involvement to decompress video signal data to rewrite the changed portions of the frame. Typically, and in low end personal computers almost certainly, processor involvement takes the form of the CPU decompressing the data stream from the auxiliary storage device and writing the changed sections of the frame stored in the video buffer.
A frame compressed by a frame-differencing algorithm consists of two separate entities. One is a mechanism to denote the addresses (or locations) in the frame of the pixels that differed from the previous frame. The second entity denotes the values of the pixels that changed (i.e., the new information). A binary bit map has typically been used to mark the pixels of a frame which differed from the previous one and which did not differ. Such a map is an M.times.N array of "1's" and "0's" corresponding to the M.times.N array of pixels in a frame. The values of the pixels which changed then follow in a sequential list.
Data so compressed reduce the amount of consumed storage, thus allowing the video data to be stored in storage devices that have low sustained read rates such as compact disk read only memory (CD-ROM) and read/write (R/W) optical storage devices. The CPU burden of reading the video data from storage and writing it to the video buffer of display adaptors such as the Extended Graphics Array (XGA) and Super Video Graphics Array (SVGA) is also reduced. Frame-differencing video decompression algorithms can be implemented in low-end personal computers with addition of programming only, because they offer a reasonable amount of data compression while simultaneously providing a data format of low computational complexity for real-time decompression and display.
Frame to frame differences have been detected by comparison of the actual numerical values of corresponding pixels in each frame. While conceptually straightforward, the technique responds to changes from frame to frame which are beyond human perception, resulting in unnecessary demands on the computer's CPU. Literal frame to frame comparison of values of each pixel, without analysis of areas of pixels, results in a process that is susceptible to noise. For example, the RGB value for a pixel may be changed by electrical interference. The pixels adjacent to the changed pixel exhibit no change. Prior techniques would preserve the error and load the CPU with the time consuming task of writing the change to the display buffer.
Additional reduction in the amount of storage consumed by compressed data, the ability to store compressed video data in storage devices that have low bandwidths, and reduction in the computational load required of the central processor are all desirable.